package backtracking;

import java.util.*;

/**
 * 332.重新安排形成
 * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
 * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
 * ● 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
 * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
 */
public class findItinerary {
    /**
     * 自己写+ai优化
     */
    LinkedList<String> path = new LinkedList<>();
    List<String> result = new ArrayList<>();
    boolean flag = false; // 标志位，表示是否已找到结果

    public  List<String> findItinerary(List<List<String>> tickets) {
        path.add("JFK");
        find(tickets, "JFK");
        return result;
    }

    public  void find(List<List<String>> tickets, String current) {
        if (flag) {
            return;
        }
        if (tickets.size() == 0) {
            result = new ArrayList<>(path);
            flag = true; // 找到一个完整的行程，设置标志位
            return;
        }

        // 收集所有从当前机场出发的目的地及对应票的索引
        Map<String, Integer> destinationMap = new TreeMap<>();
        for (int i = 0; i < tickets.size(); i++) {
            List<String> ticket = tickets.get(i);
            if (ticket.get(0).equals(current)) {
                destinationMap.put(ticket.get(1), i);
            }
        }

        if (destinationMap.isEmpty()) {
            return;
        }

        // 按字典序遍历目的地
        for (Map.Entry<String, Integer> entry : destinationMap.entrySet()) {
            if (flag) { // 已找到结果，提前返回
                return;
            }
            String dest = entry.getKey();
            int index = entry.getValue();

            path.add(dest);
            List<String> usedTicket = tickets.remove(index);
            find(tickets, dest);
            path.removeLast();
            tickets.add(index, usedTicket); // 恢复移除的票
        }
    }
}



